package com.example.lcpractice.lc;

import java.util.Arrays;

/**
 * 338. 比特位计数
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 示例 2：
 * <p>
 * 输入：n = 5
 * 输出：[0,1,1,2,1,2]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 3 --> 11
 * 4 --> 100
 * 5 --> 101
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= n <= 105
 * <p>
 * <p>
 * 进阶：
 * <p>
 * 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
 * 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
 */
public class Lc338 {


    public static void main(String[] args) {
      /*  for (int i = 1; i <= 100; i++) {
            if((i&(i-1))==0){
                System.out.println(i);
            }
        }*/
        System.out.println("=============================");

        int[] ints = new int[0];
        System.out.println(Arrays.toString(countBits2(10)));

    }

    public static int[] countBits(int n) {

        int[] re = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            re[i] = calc(i);
        }
        return re;
    }

    /**
     * 计算单个数字'1'个数
     *
     * @param num
     * @return
     */
    private static int calc(int num) {
        int bits = 0;
        while (num != 0) {
            if ((num & 1) != 0) {
                bits++;

            }
            num = num >> 1;
        }
        return bits;
    }

    /**
     * 动态规划——最高有效位【太难思路：舍弃】
     * 利用dp[12]=dp[8]+dp[12-8]
     * =1+dp[4]=2
     * 难点在于每次要记住 最大有效数 如‘8’
     *
     * @param n
     * @return
     */
    public static int[] countBits2(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            //
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }

    /**
     * 动态规划——最低有效位
     * 对于正整数 x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是 ⌊x/2⌋。如果 bits⌊ x/2⌋ 的值已知，则可以得到 bits[x] 的值：
     *
     * 如果 x 是偶数，则 bits[x]=bits[x/2]+0；
     * 如果 x 是奇数，则 bits[x]=bits[x/2]+1。
     * 上述两种情况可以合并成：bits[x] 的值等于 bits[x/2] 的值加上 x 除以 2 的余数。
     *
     * 由于 ⌊x/2⌋ 可以通过 x>>1 得到，x 除以 2 的余数可以通过 x & 1 得到，因此有：bits[x]=bits[x>>1]+(x & 1)。
     *  首先 bits[0]=0
     *   i=1,bits[1]=dp[1>>1]+1=1;
     *   i=2,bits[2]=dp[2>>1]+0=1; i=3,bits[3]=dp[3>>1]+1=2;
     *   i=4,bits[4]=dp[4>>1]+0=1; i=5,bits[5]=dp[5>>1]+1=2; i=6,bits[6]=dp[6>>1]+0=2; i=7,bits[7]=dp[7>>1]+1=3;
     * @param n
     * @return
     */
    public static int[] countBits3(int n) {
            int[] bits = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                bits[i] = bits[i >> 1] + (i & 1);
            }
            return bits;
    }

}
